// -----------------------------
// projects/c++/collatz/main.c++
// Copyright (C) 2009
// Glenn P. Downing
// -----------------------------

// To run the tests:
//     g++ -ansi -pedantic -lcppunit -ldl -Wall -DTEST main.c++ -o main.app
//     valgrind main.app

// To run the program:
//     g++ -ansi -pedantic -Wall main.c++ -o main.app
//     valgrind main.app < Collatz.in > Collatz.out

// To configure Doxygen:
//     doxygen -g
// That creates the file Doxyfile.
// Make the following edits:
//     EXTRACT_ALL            = YES
//     EXTRACT_PRIVATE        = YES
//     EXTRACT_STATIC         = YES
//     GENERATE_LATEX         = NO

// To document the program:
//     doxygen Doxyfile

// --------
// includes
// --------

#include <cassert>  // assert
#include <iostream> // cin, cout, endl, ios_base, istream, ostream

#ifdef TEST
    #include "cppunit/TestSuite.h"      // TestSuite
    #include "cppunit/TextTestRunner.h" // TestRunner
#endif // TEST

// -------
// defines
// -------

#ifdef ONLINE_JUDGE
    #define NDEBUG
#endif

// -------
// globals
// -------

int i; // input: don't change after reading
int j; // input: don't change after reading
int v; // output
int meta [5000] = { 125, 144, 142, 171, 179, 182, 177, 172, 180, 175, 170, 183, 209, 191, 217, 199, 181, 194, 238, 189, 189, 215, 184, 197, 210, 179, 192, 236, 205, 218, 262, 200, 244, 182, 257, 195, 208, 239, 221, 252, 190, 234, 203, 216, 247, 198, 260, 198, 198, 242, 224, 242, 255, 255, 268, 237, 206, 237, 219, 250, 250, 263, 263, 201, 201, 245, 276, 245, 214, 258, 196, 196, 209, 271, 240, 271, 240, 222, 253, 253, 235, 204, 266, 266, 204, 235, 235, 248, 279, 248, 186, 248, 261, 230, 261, 199, 212, 274, 243, 274, 243, 243, 243, 225, 256, 225, 256, 238, 207, 269, 269, 269, 269, 238, 207, 238, 220, 282, 251, 251, 251, 251, 202, 264, 233, 264, 246, 215, 233, 233, 202, 246, 277, 308, 246, 259, 246, 215, 259, 259, 228, 259, 228, 197, 228, 241, 272, 210, 241, 272, 272, 241, 241, 254, 210, 223, 254, 285, 285, 254, 254, 254, 267, 192, 267, 267, 236, 267, 236, 267, 236, 311, 249, 280, 205, 249, 280, 311, 324, 249, 249, 249, 249, 218, 231, 262, 262, 306, 262, 231, 244, 213, 231, 213, 244, 275, 200, 244, 275, 306, 275, 244, 213, 257, 288, 244, 213, 226, 257, 257, 226, 288, 257, 257, 239, 257, 226, 226, 239, 270, 270, 239, 239, 270, 239, 314, 239, 239, 239, 239, 252, 208, 283, 252, 252, 283, 314, 283, 252, 252, 252, 221, 252, 265, 296, 221, 265, 296, 234, 265, 234, 265, 234, 265, 278, 265, 309, 234, 234, 247, 278, 278, 340, 247, 278, 278, 309, 322, 247, 247, 247, 260, 260, 247, 216, 216, 260, 260, 260, 198, 322, 304, 291, 260, 291, 304, 229, 260, 273, 229, 211, 242, 273, 273, 198, 273, 242, 273, 273, 304, 317, 286, 273, 273, 335, 255, 242, 286, 286, 317, 255, 255, 255, 286, 286, 317, 330, 255, 255, 255, 255, 299, 224, 255, 268, 224, 224, 268, 237, 268, 268, 206, 268, 237, 237, 268, 237, 281, 312, 237, 312, 237, 312, 237, 206, 250, 250, 299, 281, 250, 281, 312, 281, 281, 312, 219, 325, 250, 250, 250, 250, 263, 219, 263, 263, 294, 294, 232, 294, 232, 263, 294, 294, 325, 232, 307, 232, 263, 232, 294, 307, 276, 201, 307, 232, 351, 232, 214, 245, 245, 276, 276, 307, 338, 245, 307, 276, 276, 214, 307, 289, 320, 245, 276, 276, 320, 245, 258, 258, 289, 245, 289, 307, 320, 289, 227, 258, 289, 289, 227, 320, 302, 289, 289, 258, 240, 289, 258, 302, 227, 302, 258, 271, 209, 227, 333, 227, 240, 271, 271, 333, 196, 271, 271, 240, 315, 302, 271, 240, 302, 284, 315, 240, 271, 271, 240, 315, 333, 240, 209, 284, 253, 284, 302, 315, 222, 284, 253, 253, 253, 284, 284, 222, 315, 302, 328, 284, 253, 284, 253, 253, 297, 266, 222, 253, 253, 266, 297, 222, 297, 222, 266, 235, 266, 284, 328, 266, 235, 328, 235, 341, 235, 266, 266, 235, 297, 279, 310, 279, 235, 266, 310, 266, 310, 235, 235, 204, 235, 248, 248, 279, 297, 279, 310, 248, 341, 217, 310, 248, 279, 279, 354, 310, 248, 323, 292, 279, 248, 279, 248, 279, 217, 261, 248, 217, 261, 292, 292, 292, 310, 292, 230, 261, 292, 230, 261, 292, 323, 292, 217, 323, 230, 305, 292, 292, 230, 261, 292, 292, 261, 199, 305, 261, 199, 261, 305, 274, 349, 323, 305, 199, 212, 305, 243, 243, 274, 199, 305, 305, 230, 336, 274, 243, 305, 318, 305, 274, 305, 243, 305, 287, 318, 287, 243, 243, 274, 274, 274, 318, 336, 256, 212, 243, 256, 318, 256, 331, 287, 305, 318, 225, 287, 287, 225, 256, 256, 318, 287, 287, 212, 256, 318, 300, 331, 300, 287, 256, 256, 238, 287, 256, 331, 300, 331, 225, 287, 300, 300, 269, 344, 300, 225, 300, 331, 225, 300, 238, 238, 269, 287, 331, 300, 194, 269, 331, 269, 313, 300, 313, 300, 269, 269, 238, 300, 269, 344, 313, 282, 269, 238, 269, 313, 207, 269, 313, 331, 251, 313, 207, 251, 282, 313, 251, 282, 282, 300, 282, 313, 238, 251, 344, 220, 326, 313, 251, 282, 282, 282, 326, 313, 282, 295, 375, 326, 282, 282, 251, 282, 282, 251, 251, 326, 295, 264, 251, 220, 264, 251, 295, 264, 295, 295, 357, 295, 220, 233, 251, 295, 233, 233, 264, 264, 295, 326, 295, 220, 233, 326, 264, 225, 370, 339, 233, 295, 264, 264, 233, 233, 295, 264, 277, 308, 277, 264, 233, 233, 264, 308, 277, 308, 352, 326, 233, 308, 264, 202, 233, 308, 246, 246, 383, 277, 295, 308, 308, 202, 277, 339, 308, 246, 246, 308, 321, 308, 277, 277, 352, 246, 308, 277, 290, 215, 370, 290, 277, 246, 277, 277, 277, 290, 277, 321, 228, 339, 259, 246, 246, 259, 321, 290, 259, 290, 334, 259, 308, 290, 321, 228, 290, 290, 352, 228, 334, 303, 259, 321, 290, 290, 228, 215, 259, 321, 228, 303, 290, 334, 259, 290, 228, 259, 290, 290, 290, 259, 259, 334, 303, 272, 334, 259, 210, 303, 272, 303, 272, 303, 347, 210, 321, 303, 334, 228, 228, 272, 303, 241, 241, 272, 272, 272, 334, 303, 303, 197, 228, 272, 334, 228, 316, 241, 347, 316, 303, 272, 272, 254, 303, 241, 303, 272, 210, 285, 365, 285, 272, 241, 210, 272, 272, 316, 272, 272, 316, 316, 334, 254, 241, 210, 241, 254, 316, 316, 179, 254, 285, 329, 210, 303, 285, 316, 316, 223, 285, 347, 285, 223, 329, 316, 254, 285, 316, 285, 316, 254, 223, 254, 316, 254, 241, 360, 329, 298, 285, 285, 254, 254, 241, 329, 298, 285, 254, 329, 272, 347, 267, 329, 254, 223, 285, 298, 329, 267, 267, 223, 342, 298, 223, 360, 298, 329, 223, 236, 267, 298, 236, 236, 236, 267, 267, 285, 329, 298, 329, 298, 236, 267, 267, 329, 236, 228, 311, 342, 311, 267, 298, 267, 267, 254, 236, 311, 298, 267, 342, 342, 236, 311, 280, 267, 267, 205, 280, 311, 311, 205, 280, 267, 311, 355, 329, 280, 311, 236, 342, 236, 373, 311, 311, 311, 249, 280, 280, 280, 280, 311, 280, 280, 311, 218, 236, 280, 342, 249, 249, 324, 249, 355, 280, 311, 280, 311, 280, 262, 355, 324, 311, 280, 249, 293, 298, 373, 293, 249, 280, 249, 249, 280, 280, 280, 218, 280, 280, 386, 324, 231, 342, 262, 324, 249, 187, 249, 262, 324, 293, 262, 262, 293, 337, 293, 311, 355, 293, 280, 324, 231, 249, 293, 355, 262, 231, 337, 262, 262, 262, 293, 324, 293, 324, 293, 218, 262, 231, 324, 262, 231, 223, 368, 337, 293, 231, 293, 262, 262, 368, 249, 231, 306, 231, 293, 262, 218, 337, 355, 306, 275, 262, 262, 231, 262, 306, 306, 306, 275, 275, 443, 306, 350, 213, 324, 231, 306, 231, 337, 262, 293, 275, 368, 306, 275, 244, 275, 275, 381, 275, 293, 337, 306, 306, 306, 231, 231, 275, 337, 306, 306, 275, 319, 306, 350, 319, 275, 306, 275, 275, 275, 257, 350, 244, 244, 306, 275, 200, 293, 244, 368, 288, 244, 275, 244, 275, 244, 275, 275, 319, 213, 288, 275, 319, 319, 226, 337, 244, 257, 244, 213, 275, 244, 257, 244, 319, 257, 257, 257, 288, 332, 288, 257, 350, 319, 288, 319, 257, 226, 244, 288, 288, 350, 257, 244, 332, 257, 319, 332, 288, 319, 288, 257, 319, 288, 226, 213, 257, 257, 319, 288, 244, 301, 306, 332, 301, 288, 288, 288, 257, 226, 363, 288, 288, 288, 226, 288, 257, 257, 332, 275, 257, 345, 270, 332, 257, 257, 195, 288, 301, 195, 301, 195, 270, 270, 301, 345, 301, 208, 319, 239, 332, 301, 332, 301, 239, 288, 270, 301, 270, 239, 239, 407, 270, 270, 270, 288, 332, 270, 301, 332, 301, 226, 239, 270, 270, 332, 270, 301, 239, 314, 239, 345, 314, 270, 301, 270, 270, 239, 270, 257, 239, 345, 239, 314, 270, 345, 226, 440, 239, 363, 345, 283, 270, 270, 239, 270, 239, 270, 208, 314, 208, 283, 283, 270, 314, 358, 314, 332, 239, 252, 314, 314, 345, 221, 252, 252, 283, 314, 283, 314, 252, 252, 283, 283, 389, 283, 301, 345, 239, 283, 314, 314, 239, 239, 283, 283, 345, 314, 283, 221, 327, 252, 314, 358, 327, 283, 314, 283, 252, 314, 283, 265, 358, 327, 252, 314, 283, 283, 283, 358, 301, 376, 327, 296, 283, 283, 283, 252, 221, 314, 283, 283, 327, 296, 221, 283, 283, 327, 389, 422, 252, 345, 252, 265, 327, 252, 221, 190, 252, 327, 296, 327, 296, 296, 265, 265, 221, 296, 340, 296, 203, 358, 221, 296, 296, 327, 252, 234, 296, 265, 296, 358, 234, 265, 234, 265, 265, 327, 309, 265, 296, 296, 327, 296, 327, 296, 265, 221, 234, 265, 371, 327, 296, 234, 221, 234, 371, 234, 340, 309, 265, 265, 296, 265, 265, 296, 265, 252, 247, 340, 234, 327, 296, 265, 340, 221, 340, 247, 309, 309, 278, 265, 265, 265, 265, 203, 278, 265, 309, 309, 309, 203, 278, 278, 265, 309, 371, 309, 216, 327, 234, 247, 309, 234, 340, 265, 234, 371, 278, 309, 371, 278, 309, 265, 247, 278, 278, 384, 278, 353, 309, 340, 309, 278, 278, 309, 278, 234, 234, 278, 278, 340, 309, 278, 247, 239, 322, 247, 353, 309, 322, 278, 309, 247, 278, 309, 278, 278, 309, 353, 322, 247, 247, 322, 278, 278, 265, 353, 296, 247, 371, 353, 291, 247, 278, 260, 247, 247, 309, 278, 234, 322, 322, 291, 291, 278, 278, 322, 384, 322, 229, 291, 340, 247, 260, 322, 247, 247, 229, 247, 216, 291, 322, 322, 291, 322, 260, 260, 260, 291, 291, 353, 291, 260, 309, 353, 291, 291, 291, 322, 247, 229, 247, 291, 260, 291, 353, 322, 260, 247, 335, 291, 260, 322, 322, 335, 291, 322, 291, 291, 260, 322, 291, 260, 216, 322, 366, 260, 322, 291, 291, 229, 247, 366, 309, 291, 335, 304, 260, 291, 291, 260, 260, 291, 260, 366, 291, 242, 304, 291, 229, 304, 260, 260, 335, 216, 335, 278, 353, 304, 260, 273, 335, 260, 304, 229, 229, 260, 291, 304, 260, 273, 304, 198, 273, 441, 260, 304, 304, 348, 304, 211, 322, 229, 242, 304, 304, 335, 229, 260, 242, 291, 273, 242, 366, 304, 273, 304, 242, 242, 273, 273, 379, 273, 348, 304, 291, 335, 304, 273, 335, 304, 273, 229, 229, 229, 273, 348, 335, 304, 304, 379, 242, 379, 322, 242, 348, 304, 317, 304, 273, 304, 273, 242, 242, 273, 379, 304, 348, 348, 242, 229, 317, 317, 273, 348, 229, 443, 291, 255, 366, 348, 286, 273, 273, 273, 242, 361, 242, 273, 242, 273, 229, 273, 317, 286, 211, 286, 286, 242, 317, 361, 317, 317, 224, 335, 242, 255, 317, 317, 348, 242, 286, 242, 255, 255, 286, 317, 317, 286, 317, 348, 255, 361, 286, 286, 392, 286, 286, 255, 304, 348, 317, 317, 286, 317, 317, 286, 224, 242, 286, 255, 286, 348, 286, 286, 317, 255, 255, 330, 286, 317, 361, 330, 286, 286, 317, 255, 286, 423, 317, 286, 255, 242, 361, 317, 330, 255, 255, 317, 286, 286, 361, 242, 361, 304, 242, 379, 286, 299, 286, 255, 286, 255, 374, 224, 237, 361, 286, 317, 286, 330, 299, 224, 299, 286, 286, 255, 330, 330, 330, 273, 237, 348, 255, 268, 255, 330, 255, 224, 255, 224, 268, 286, 299, 255, 330, 299, 299, 193, 268, 436, 255, 224, 299, 361, 299, 237, 206, 317, 361, 237, 330, 299, 224, 330, 299, 255, 237, 286, 260, 268, 299, 361, 299, 361, 255, 237, 255, 405, 299, 268, 312, 268, 268, 299, 299, 330, 299, 299, 268, 330, 299, 268, 224, 268, 224, 343, 374, 268, 330, 299, 299, 299, 255, 237, 374, 237, 299, 343, 299, 387, 268, 268, 299, 268, 268, 268, 237, 268, 250, 255, 237, 299, 343, 237, 330, 312, 299, 299, 343, 224, 343, 438, 250, 237, 361, 343, 281, 268, 343, 268, 268, 237, 268, 268, 281, 299, 312, 237, 312, 312, 268, 206, 281, 281, 449, 268, 312, 374, 356, 312, 219, 330, 281, 237, 250, 312, 312, 312, 343, 206, 268, 237, 374, 312, 281, 312, 374, 281, 281, 312, 268, 250, 250, 281, 281, 343, 387, 343, 281, 299, 312, 343, 281, 312, 281, 281, 343, 281, 237, 219, 237, 281, 281, 281, 281, 343, 312, 312, 281, 219, 268, 325, 281, 281, 356, 312, 325, 281, 281, 312, 250, 281, 418, 312, 281, 281, 281, 312, 356, 312, 325, 356, 250, 312, 281, 281, 250, 356, 237, 356, 299, 250, 374, 325, 281, 294, 281, 250, 281, 281, 250, 250, 281, 232, 312, 281, 281, 281, 281, 325, 294, 312, 294, 343, 281, 250, 325, 387, 420, 268, 250, 250, 343, 250, 263, 338, 325, 312, 356, 250, 232, 219, 250, 281, 325, 294, 325, 325, 294, 294, 387, 263, 263, 263, 294, 294, 294, 400, 294, 294, 325, 312, 356, 219, 232, 294, 294, 294, 325, 263, 250, 263, 250, 294, 294, 263, 294, 356, 263, 325, 294, 232, 250, 338, 281, 263, 325, 307, 325, 338, 294, 294, 276, 325, 294, 294, 263, 325, 294, 263, 263, 219, 232, 325, 263, 369, 263, 338, 294, 263, 263, 369, 250, 232, 369, 263, 250, 387, 276, 307, 263, 294, 263, 294, 263, 263, 276, 294, 263, 369, 245, 294, 294, 294, 338, 338, 232, 325, 307, 263, 263, 338, 338, 219, 338, 281, 232, 356, 351, 263, 276, 263, 338, 263, 263, 307, 232, 263, 263, 276, 294, 307, 307, 263, 307, 307, 276, 201, 276, 276, 444, 232, 307, 307, 369, 307, 245, 307, 276, 325, 232, 245, 276, 307, 307, 232, 338, 201, 263, 245, 263, 369, 307, 276, 307, 369, 276, 307, 369, 307, 294, 245, 413, 276, 276, 276, 382, 276, 351, 294, 294, 307, 338, 307, 307, 276, 276, 307, 307, 276, 232, 232, 232, 276, 276, 263, 276, 338, 307, 307, 307, 307, 294, 276, 382, 245, 245, 307, 351, 307, 320, 276, 263, 276, 307, 276, 276, 245, 307, 276, 276, 382, 307, 245, 351, 351, 320, 245, 338, 320, 320, 276, 276, 351, 263, 351, 446, 294, 245, 232, 369, 351, 289, 382, 276, 351, 276, 276, 258, 258, 245, 289, 227, 307, 276, 232, 214, 320, 320, 289, 320, 289, 289, 338, 276, 289, 320, 214, 382, 415, 227, 227, 338, 338, 382, 258, 258, 320, 320, 307, 351, 245, 227, 276, 245, 307, 320, 320, 320, 320, 320, 289, 320, 320, 258, 258, 426, 258, 245, 320, 289, 395, 351, 289, 289, 289, 307, 351, 214, 320, 320, 289, 320, 320, 320, 289, 214, 258, 245, 245, 289, 258, 289, 289, 351, 320, 258, 289, 245, 245, 276, 333, 395, 289, 320, 364, 302, 333, 289, 320, 289, 320, 289, 289, 426, 258, 320, 289, 289, 258, 271, 227, 320, 271, 333, 364, 258, 258, 320, 289, 289, 289, 364, 245, 245, 364, 307, 258, 382, 333, 289, 302, 302, 364, 258, 333, 289, 258, 377, 258, 302, 240, 258, 364, 289, 245, 289, 289, 333, 302, 227, 320, 302, 470, 289, 258, 333, 333, 214, 333, 276, 258, 240, 351, 346, 258, 271, 364, 333, 258, 395, 302, 258, 227, 227, 258, 271, 289, 302, 302, 258, 333, 271, 302, 302, 271, 271, 271, 439, 258, 258, 302, 302, 364, 302, 302, 302, 333, 320, 302, 364, 240, 333, 302, 302, 227, 333, 271, 302, 258, 271, 258, 289, 302, 271, 271, 302, 364, 302, 271, 364, 408, 240, 258, 302, 408, 302, 271, 333, 377, 302, 346, 302, 302, 302, 333, 271, 302, 377, 271, 333, 302, 302, 271, 271, 227, 240, 333, 346, 271, 258, 346, 271, 333, 302, 302, 302, 377, 240, 258, 377, 320, 258, 240, 302, 346, 302, 315, 302, 271, 284, 302, 271, 271, 271, 333, 302, 240, 271, 377, 302, 258, 209, 346, 346, 240, 240, 240, 333, 315, 271, 271, 302, 346, 227, 227, 441, 284, 289, 240, 364, 315, 346, 271, 284, 271, 346, 271, 271, 315, 240, 359, 240, 271, 284, 302, 307, 315, 240, 315, 271, 315, 346, 209, 284, 284, 284, 452, 271, 240, 315, 315, 377, 315, 315, 315, 222, 333, 328, 240, 240, 253, 284, 315, 302, 315, 346, 240, 271, 284, 240, 377, 302, 315, 284, 271, 315, 315, 284, 315, 284, 315, 346, 253, 421, 359, 284, 284, 284, 346, 390, 284, 359, 191, 315, 315, 302, 346, 271, 315, 284, 284, 284, 315, 315, 284, 284, 240, 253, 240, 284, 284, 253, 284, 284, 359, 346, 315, 284, 315, 222, 271, 271, 328, 253, 284, 253, 315, 359, 315, 328, 253, 284, 284, 253, 315, 253, 284, 421, 328, 315, 284, 284, 284, 266, 253, 222, 359, 359, 328, 359, 253, 346, 315, 284, 315, 284, 284, 359, 271, 240, 359, 302, 266, 253, 377, 328, 284, 284, 297, 284, 359, 253, 284, 284, 266, 372, 253, 297, 284, 253, 359, 253, 328, 315, 284, 253, 328, 297, 328, 222, 315, 297, 346, 284, 253, 328, 328, 390, 372, 423, 271, 253, 235, 346, 341, 253, 315, 266, 359, 328, 253, 328, 253, 222, 253, 253, 253, 266, 266, 284, 328, 297, 297, 328, 328, 297, 328, 297, 328, 266, 266, 434, 266, 372, 266, 297, 297, 359, 297, 359, 297, 328, 315, 315, 359, 222, 235, 328, 297, 297, 284, 266, 328, 266, 297, 315, 266, 253, 297, 235, 297, 297, 297, 297, 359, 297, 328, 359, 235, 328, 235, 284, 403, 284, 297, 266, 328, 310, 328, 328, 266, 297, 297, 297, 279, 328, 297, 297, 266, 266, 328, 297, 297, 279, 266, 372, 222, 266, 266, 341, 266, 372, 266, 266, 341, 297, 297, 297, 297, 372, 253, 253, 235, 372, 315, 235, 279, 297, 341, 403, 310, 385, 372, 279, 266, 297, 297, 266, 266, 279, 235, 297, 266, 266, 372, 297, 253, 235, 248, 297, 341, 310, 235, 328, 328, 310, 279, 297, 266, 266, 341, 222, 222, 436, 341, 341, 266, 248, 359, 310, 341, 279, 279, 266, 341, 266, 266, 341, 310, 266, 354, 235, 266, 279, 235, 297, 310, 310, 266, 310, 235, 310, 279, 310, 279, 279, 279, 279, 447, 266, 266, 310, 310, 372, 354, 310, 248, 310, 217, 328, 323, 372, 235, 248, 248, 310, 310, 279, 310, 341, 235, 204, 266, 248, 235, 372, 297, 310, 279, 279, 310, 310, 372, 310, 271, 310, 310, 266, 248, 310, 271, 354, 279, 279, 279, 341, 385, 279, 341, 354, 310, 279, 310, 341, 509, 310, 310, 279, 279, 310, 279, 341, 310, 279, 248, 235, 235, 235, 235, 279, 279, 279, 279, 279, 341, 292, 310, 310, 310, 310, 217, 266, 279, 385, 328, 279, 279, 279, 354, 248, 310, 323, 279, 310, 292, 279, 310, 279, 279, 279, 416, 248, 310, 248, 279, 279, 279, 310, 310, 217, 354, 310, 354, 248, 354, 248, 341, 323, 279, 279, 279, 279, 354, 354, 266, 354, 449, 297, 261, 248, 235, 372, 323, 416, 292, 292, 279, 354, 248, 235, 279, 261, 248, 248, 261, 248, 279, 230, 310, 230, 279, 310, 279, 323, 323, 323, 292, 292, 217, 310, 292, 292, 341, 279, 248, 248, 323, 217, 385, 418, 323, 266, 323, 230, 292, 341, 292, 292, 261, 336, 248, 323, 248, 310, 354, 354, 248, 279, 336, 248, 261, 385, 310, 323, 292, 248, 323, 323, 323, 292, 323, 292, 385, 354, 261, 261, 429, 261, 230, 323, 292, 292, 354, 398, 354, 292, 292, 323, 305, 310, 217, 354, 217, 292, 323, 292, 292, 279, 292, 323, 261, 292, 292, 230, 261, 248, 248, 292, 292, 261, 261, 292, 292, 367, 292, 323, 323, 292, 292, 345, 279, 248, 398, 323, 292, 261, 261, 323, 305, 367, 323, 336, 292, 292, 292, 274, 323, 292, 292, 292, 261, 261, 261, 323, 292, 292, 261, 323, 323, 217, 261, 323, 323, 336, 367, 261, 261, 261, 336, 323, 292, 292, 292, 367, 367, 248, 248, 230, 367, 310, 261, 274, 385, 336, 292, 292, 305, 305, 292, 292, 261, 248, 336, 261, 261, 336, 380, 230, 292, 243, 261, 367, 230, 336, 323, 292, 336, 336, 336, 292, 336, 230, 323, 305, 305, 305, 305, 261, 261, 336, 336, 230, 380, 336, 336, 279, 261, 243, 354, 349, 261, 261, 261, 274, 261, 336, 336, 398, 261, 367, 305, 261, 307, 261, 199, 274, 274, 292, 336, 305, 305, 261, 336, 336, 305, 336, 274, 336, 199, 274, 274, 274, 442, 261, 230, 305, 305, 323, 367, 349, 305, 305, 305, 212, 212, 323, 274, 367, 274, 243, 336, 274, 305, 305, 292, 305, 336, 336, 305, 318, 261, 243, 261, 367, 199, 305, 274, 274, 274, 305, 367, 274, 305, 336, 367, 305, 305, 243, 305, 243, 349, 411, 274, 274, 274, 336, 380, 336, 274, 349, 305, 305, 274, 305, 287, 336, 504, 305, 380, 274, 274, 305, 336, 305, 305, 243, 274, 230, 230, 243, 274, 274, 349, 274, 261, 274, 349, 274, 336, 287, 305, 305, 305, 305, 380, 292, 261, 274, 380, 323, 261, 274, 243, 305, 349, 287, 411, 318, 274, 305, 380, 287, 243, 305, 274, 274, 274, 243, 274, 243, 305, 256, 274, 380, 243, 305, 336, 305, 349, 305, 349, 318, 318, 243, 243, 336, 318, 318, 274, 305, 274, 274, 349, 230, 261, 349, 444, 349, 292, 274, 243, 318, 367, 318, 411, 274, 367, 380, 274, 349, 256, 243, 274, 243, 256, 274, 362, 243, 212, 287, 287, 243, 305, 310, 318, 274, 274, 349, 318, 318, 287, 287, 318, 212, 287, 287, 287, 362, 287, 243, 287, 318, 318, 380, 380, 413, 318, 243, 318, 243, 225, 336, 331, 380, 349, 256, 256, 287, 318, 318, 305, 243, 349, 349, 287, 212, 287, 243, 243, 256, 380, 424, 318, 287, 318, 287, 318, 318, 287, 380, 318, 287, 318, 349, 256, 256, 274, 424, 424, 243, 318, 287, 287, 349, 393, 349, 287, 362, 287, 318, 318, 318, 212, 349, 212, 287, 318, 318, 287, 287, 318, 287, 318, 318, 256, 287, 300, 243, 256, 243, 243, 349, 287, 256, 256, 287, 287, 287, 349, 300, 362, 318, 287, 318, 287, 225, 274, 274, 256, 393, 393, 287, 256, 256, 318, 362, 300, 318, 331, 256, 318, 269, 287, 225, 318, 287, 305, 287, 287, 424, 331, 318, 256, 287, 287, 256, 269, 318, 318, 256, 362, 318, 362, 331, 256, 362, 256, 349, 331, 331, 287, 318, 287, 287, 287, 362, 243, 243, 243, 256, 362, 305, 287, 256, 243, 380, 331, 269, 287, 300, 300, 287, 362, 256, 238, 331, 287, 256, 269, 256, 375, 300, 300, 287, 238, 256, 362, 300, 287, 318, 331, 287, 287, 331, 331, 300, 300, 225, 225, 318, 300, 287, 468, 300, 256, 256, 331, 331, 287, 393, 375, 426, 269, 331, 256, 238, 238, 349, 344, 256, 256, 269, 269, 362, 256, 331, 256, 393, 256, 362, 238, 256, 331, 225, 256, 331, 269, 207, 437, 331, 300, 300, 256, 331, 331, 300, 300, 300, 300, 393, 269, 269, 269, 269, 437, 256, 256, 300, 331, 300, 300, 362, 362, 344, 507, 300, 300, 194, 331, 318, 269, 300, 362, 225, 287, 331, 269, 300, 300, 287, 300, 331, 331, 269, 300, 313, 256, 238, 300, 256, 300, 375, 300, 269, 300, 269, 300, 300, 362, 269, 331, 331, 362, 269, 406, 300, 238, 256, 300, 406, 225, 300, 269, 287, 331, 375, 331, 300, 269, 344, 269, 300, 331, 300, 282, 331, 437, 300, 300, 375, 269, 269, 269, 331, 300, 300, 300, 269, 282, 331, 225, 238, 269, 468, 344, 344, 331, 375, 344, 269, 269, 344, 331, 300, 300, 300, 300, 300, 375, 238, 256, 230, 375, 375, 318, 282, 269, 282, 393, 344, 300, 406, 300, 313, 388, 300, 251, 282, 251, 300, 269, 269, 251, 269, 238, 331, 313, 300, 238, 331, 269, 375, 251, 300, 256, 300, 344, 300, 300, 406, 300, 238, 238, 238, 331, 313, 313, 313, 300, 300, 269, 300, 344, 238, 406, 225, 388, 439, 282, 287, 251, 238, 251, 362, 357, 344, 269, 269, 362, 375, 269, 344, 269, 220, 269, 269, 313, 238, 238, 357, 269, 238, 344, 282, 220, 300, 344, 313, 313, 313, 269, 344, 269, 282, 313, 344, 313, 450, 300, 282, 282, 282, 357, 450, 269, 238, 313, 313, 313, 313, 375, 357, 313, 520, 313, 313, 238, 331, 331, 326, 282, 375, 238, 251, 326, 282, 313, 313, 313, 313, 313, 344, 344, 282, 313, 282, 251, 238, 282, 375, 419, 207, 313, 282, 282, 274, 313, 313, 375, 282, 375, 274, 344, 313, 282, 344, 251, 251, 251, 419, 357, 238, 282, 282, 282, 282, 344, 388, 313, 282, 344, 357, 238, 313, 282, 313, 295, 344, 207, 295, 220, 313, 282, 282, 282, 313, 282, 344, 313, 251, 282, 525, 282, 238, 251, 313, 344, 220, 282, 282, 388, 251, 282, 282, 282, 357, 282, 344, 313, 251, 313, 313, 238, 251, 269, 269, 282, 388, 331, 282, 282, 282, 251, 313, 357, 313, 357, 326, 326, 401, 313, 251, 282, 220, 313, 313, 282, 264, 282, 419, 282, 326, 313, 251, 282, 282, 264, 313, 313, 313, 269, 251, 357, 313, 313, 357, 251, 357, 357, 251, 344, 264, 326, 326, 282, 313, 282, 313, 282, 357, 269, 269, 238, 452, 357, 251, 300, 251, 251, 264, 388, 326, 264, 357, 282, 375, 295, 282, 282, 357, 282, 233, 282, 282, 264, 251, 251, 370, 295, 295, 282, 295, 233, 251, 357, 251, 326, 282, 313, 220, 326, 251, 326, 326, 295, 295, 326, 220, 313, 295, 295, 344, 295, 295, 251, 326, 251, 326, 326, 282, 388, 370, 421, 326, 269, 326, 251, 233, 295, 344, 295, 326, 251, 313, 264, 357, 295, 326, 326, 313, 388, 251, 357, 295, 251, 326, 295, 251, 264, 264, 282, 202, 432, 326, 295, 295, 326, 295, 326, 326, 326, 295, 326, 326, 295, 388, 264, 357, 251, 264, 264, 432, 264, 370, 295, 326, 295, 295, 295, 401, 339, 357, 357, 295, 295, 295, 326, 295, 326, 264, 357, 220, 344, 295, 326, 326, 295, 295, 282, 295, 295, 326, 326, 264, 295, 295, 251, 313, 264, 251, 251, 295, 370, 295, 282, 282, 295, 295, 295, 357, 370, 326, 326, 326, 264, 357, 264, 401, 233, 282, 282, 256, 401, 282, 264, 295, 264, 264, 326, 370, 326, 308, 370, 339, 264, 277, 326, 264, 295, 277, 264, 326, 295, 295, 295, 295, 264, 264, 264, 326, 264, 295, 295, 277, 264, 295, 370, 264, 220, 264, 220, 326, 326, 339, 251, 370, 282, 251, 264, 339, 339, 277, 295, 339, 295, 295, 295, 370, 295, 251, 251, 225, 233, 370, 313, 383, 401, 233, 277, 388, 339, 295, 401, 295, 308, 383, 295, 370, 277, 264, 246, 295, 295, 264, 264, 264, 339, 383, 264, 233, 295, 233, 264, 445, 370, 308, 339, 295, 326, 326, 295, 295, 233, 339, 370, 308, 339, 233, 308, 326, 233, 308, 295, 476, 308, 264, 295, 295, 339, 339, 233, 220, 383, 434, 339, 401, 339, 246, 264, 246, 357, 352, 308, 339, 264, 264, 277, 370, 277, 339, 339, 264, 233, 264, 339, 308, 251, 264, 352, 264, 233, 264, 339, 277, 277, 233, 295, 339, 308, 308, 339, 432, 339, 339, 308, 308, 339, 308, 308, 277, 339, 277, 277, 277, 277, 445, 308, 383, 233, 308, 308, 308, 308, 370, 370, 308, 308, 515, 308, 308, 202, 339, 277, 326, 321, 233, 370, 233, 476, 321, 339, 308, 308, 383, 233, 308, 308, 339, 339, 202, 308, 308, 339, 326, 264, 264, 264, 370, 246, 308, 277, 277, 233, 277, 308, 308, 370, 308, 277, 308, 339, 277, 370, 308, 414, 295, 295, 308, 269, 269, 414, 246, 277, 321, 277, 277, 339, 383, 339, 277, 339, 339, 352, 445, 308, 277, 295, 308, 290, 339, 507, 308, 308, 308, 383, 277, 277, 277, 339, 277, 339, 308, 246, 277, 277, 339, 264, 233, 277, 233, 339, 339, 352, 277, 277, 383, 277, 352, 277, 277, 352, 277, 308, 352, 308, 339, 383, 308, 383, 264, 295, 264, 277, 246, 383, 326, 277, 277, 246, 277, 308, 352, 246, 308, 308, 321, 321, 414, 308, 308, 383, 277, 246, 308, 277, 414, 277, 277, 277, 414, 277, 246, 308, 246, 277, 277, 277, 383, 308, 308, 308, 339, 308, 352, 308, 246, 352, 321, 321, 352, 246, 264, 339, 246, 321, 321, 277, 308, 277, 277, 308, 277, 352, 352, 264, 233, 352, 447, 352, 246, 295, 259, 246, 259, 233, 370, 383, 259, 414, 277, 290, 290, 383, 277, 352, 352, 259, 228, 277, 277, 321, 259, 246, 308, 365, 277, 308, 277, 290, 308, 228, 308, 228, 321, 321, 277, 308, 277, 352, 321, 321, 321, 321, 290, 290, 458, 215, 308, 290, 352, 290, 339, 290, 277, 246, 246, 290, 321, 321, 321, 383, 383, 365, 416, 321, 321, 334, 246, 321, 228, 339, 339, 334, 246, 383, 246, 259, 259, 334, 259, 321, 321, 246, 383, 321, 352, 352, 290, 290, 321, 334, 290, 246, 246, 259, 259, 383, 427, 259, 321, 290, 259, 321, 321, 321, 321, 383, 321, 383, 321, 308, 290, 383, 277, 352, 259, 259, 321, 427, 290, 365, 246, 290, 321, 290, 290, 290, 352, 396, 290, 352, 352, 290, 290, 290, 321, 303, 308, 321, 215, 352, 215, 215, 290, 321, 321, 290, 290, 290, 321, 290, 290, 321, 321, 259, 290, 290, 352, 290, 228, 259, 246, 246, 184, 365, 365, 290, 277, 277, 290, 290, 290, 365, 365, 290, 352, 321, 321, 290, 352, 321, 321, 343, 259, 277, 277, 246, 396, 321, 396, 290, 290, 259 }; // metacache in slices of 200 from 1 to 1,000,000
int lazy [1000000]; // lazy cache

// int start = 0;

// ----
// read
// ----

/**
 * reads an int into i and j
 * @return true if that succeeds, false otherwise
 */
bool read (std::istream& in) {
    if (!(in >> i))
        return false;
    in >> j;
    return true;}
// 	if ( start < 1000000 ) {
// 		i = start + 1;
// 		start += 200;
// 		j = start;
// 		return true;
// 	}
// 	return false;}

// --------
// cycleLen
// --------



/**
 * @return cycle length of n
 */
int cycleLen (int orig) {
	int c = 1;
	unsigned long n = orig;
	if (n < 5000000 && lazy[n] != 0) 
		return lazy[n];
	
	while (n != 1) {
		if (n % 2 == 1 ) {
			n = n + (n >> 1) + 1;
			c += 2;
		}
		else  {
			n /= 2;
			c++;
		}
	}
	if (orig < 5000000)
		lazy[orig] = c;
	return c;}

// ----
// eval
// ----

/**
 * computes the max cycle length in the range [i, j]
 * and stores the result in v
 */
void eval () {
	v = 0;
	int cur, beg, end;
	if (i < j) {
		beg = i;
		end = j;
	} else {
		beg = j;
		end = i;
	}
	// compute max cycle len until able to use metacache (i.e. have multiple of 100)
	int k;
// 	for ( k = beg; k <= end; k++ ) {
// 		cur = cycleLen(k);
// 		if (cur > v)
// 			v = cur;
// 	}

	for ( k = beg; k % 200 != 0 && k <= end; k++ ) {
		cur = cycleLen(k);
		if (cur > v)
			v = cur;
	}
	if (k >= end)
		return;

	// use metacache wtih slices of 200
	for (k = k / 200; k * 200 <= end && (end - (k * 200)) > 200 && k < 5000; k++ ) {
		cur = meta[k];
		if (cur > v)
			v = cur;
	}
	// continue computing max cycle len
	for (k = k * 200; k <= end; k++ ) {
		cur = cycleLen(k);
		if (cur > v)
			v = cur;
	}
}

// -----
// print
// -----

/**
 * prints the values of i, j, and v
 */
void print (std::ostream& out) {
    out << i << " " << j << " " << v << std::endl;}
// 	out << v << ", "; }

// -----
// tests
// -----

#ifdef TEST
    #include "TestCollatz.h"
#endif // TEST

// ----
// main
// ----

/**
 * either runs the tests or runs the program
 */
int main () {
    // TODO(Take out timing code)
    clock_t start = clock();

    using namespace std;
    ios_base::sync_with_stdio(false); // turn off synchronization with C I/O

    #ifdef TEST
        // ----------
        // unit tests
        // ----------

        CppUnit::TextTestRunner tr;
        tr.addTest(TestCollatz::suite());
        tr.run();
    #else
        // -------
        // program
        // -------

        while (read(cin)) {
            eval();
            print(cout);}
    #endif // TEST

    printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);

    return 0;}
